package leetcode;

import java.util.ArrayList;

/**
 * http://leetcode.com/onlinejudge
 * 
 * Permutations
 * 
 * Given a collection of numbers, return all possible permutations.
 * 
 * For example, [1,2,3] have the following permutations: [1,2,3], [1,3,2],
 * [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
 * 
 * @author yunzhang
 * 
 */
public class Permutations {
	public ArrayList<ArrayList<Integer>> permute(int[] num) {
		return permute(num, 0);
	}

	private ArrayList<ArrayList<Integer>> permute(int[] num, int n) {
		if (n == num.length - 1) {
			ArrayList<Integer> l = new ArrayList<Integer>();
			l.add(num[n]);
			ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
			res.add(l);
			return res;
		}

		ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
		for (int j = n; j < num.length; ++j) {
			swap(num, n, j);

			ArrayList<ArrayList<Integer>> subRes = permute(num, n + 1);
			for (ArrayList<Integer> p : subRes) {
				p.add(0, num[n]);
				res.add(p);
			}

			swap(num, n, j);
		}

		return res;
	}

	private void swap(int[] num, int i, int j) {
		if (i != j) {
			num[i] = num[i] ^ num[j];
			num[j] = num[i] ^ num[j];
			num[i] = num[i] ^ num[j];
		}
	}
}
